package 算法;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * @author zhangmin
 * @create 2021-12-08 19:12
 */
public class DP02 {
    /**==============================================================================================================================================
     * JZ42 连续子数组的最大和
     * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
     * dp:dp[i]表示以第i个元素结尾的子数组的最大和
     *  */
    public int FindGreatestSumOfSubArray1(int[] array) {
        int n= array.length;
        int[] dp=new int[n];
        dp[0]=array[0];
        int res=dp[0];
        for (int i = 1; i < n; i++) {
            dp[i]=Math.max(dp[i-1]+array[i],array[i]);
            res=Math.max(res,dp[i]);
        }
        return res;
    }
    //状态压缩
    public int FindGreatestSumOfSubArray2(int[] array) {
        int n= array.length;
        int dp=array[0],res=dp;
        for (int i = 1; i < n; i++) {
            dp=Math.max(dp+array[i],array[i]);
            res=Math.max(res,dp);
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ85 连续子数组的最大和(二)
     * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
     * len[i][0]表示第i个元素的选择构成的以i结尾的子数组的左边界(包括i本身)
     *  */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        int n= array.length;
        int[] dp=new int[n];
        dp[0]=array[0];
        int res=dp[0];
        int[] len=new int[n];
        len[0]=1;
        for (int i = 1; i < n; i++) {
            if (dp[i-1]+array[i]>=array[i]){
                dp[i]=dp[i-1]+array[i];
                len[i]=len[i-1]+1;
            }else {
                dp[i]=array[i];
                len[i]=1;
            }
            res=Math.max(res,dp[i]);
        }
        LinkedList<int[]> list=new LinkedList<>();
        list.addLast(new int[]{array[0]});
        for (int i = 0; i < n; i++) {
            if (res==dp[i]){
                if (len[i]>=list.getLast().length){
                    int[] resi=new int[len[i]];
                    int index=len[i]-1;
                    for (int j = i; j >i-len[i] ; j--) {
                        resi[index--]=array[j];
                    }
                    list.addLast(resi);
                }
            }
        }
        return list.getLast();
    }

    /**==============================================================================================================================================
     * JZ69 跳台阶
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
     * dp[i]表示前i个台阶一共有多少中跳法
     *  */
    public int jumpFloor(int target) {
        if (target<=2)return target;

        int[] dp=new int[target];
        dp[0]=1;dp[1]=2;
        for (int i = 2; i < target; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[target-1];
    }

    /**==============================================================================================================================================
     * JZ10 斐波那契数列
     * 大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
     *  */
    public int Fibonacci(int n) {
        if(n<=2) return 1;
        int f_1=1,f_2=1;
        for (int i = 3; i <= n; i++) {
            int t=f_1+f_2;
            f_1=f_2;f_2=t;
        }
        return f_2;
    }

    /**==============================================================================================================================================
     * JZ19 正则表达式匹配
     * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
     * 递归的匹配：dp(s,i,p,j)表示s[i...]与p[j...]是否匹配
     * s[i]与p[j]匹配：s[i]==p[j]或者p[j]为”。“万金油匹配
     * 1.1 p[j+1]有*匹配，考虑匹配0次（i不变，j+2）或多次（i++，j不变）
     * 1.2 没有*匹配，普通匹配：i++，j++
     * s[i]与p[j]不匹配：
     * 2.1 p[j+1]有*，则*匹配0次：i不变，j+2
     * 2.2 p[j+1]没有*,则完全没法匹配，返回false
     *
     * 终止条件：
     * 1.当p到了末尾，判断s是否到末尾即可
     * 2.当s到了末尾，需要判断剩下的p是否可以匹配空串
     *  */
    boolean dp(String s,int i,String p,int j){
        int m=s.length(),n=p.length();
        if (j==n){
            //1.p到了末尾
            return i==m;
        }
        if (i==m){
            //2s到了最后,可匹配空串，必顶为a*b*这种模式
            if ((n-j)%2==1)return false;
            for (; j+1 < n; j+=2) {
                if (p.charAt(j+1)!='*') return false;
            }
            return true;
        }

        boolean res=false;
        if (s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){
            if (j+1<n&&p.charAt(j+1)=='*'){
                //1.1
                res=dp(s,i,p,j+2)||dp(s,i+1,p,j);
            }else {
                //1.2
                res=dp(s,i+1,p,j+1);
            }
        }else {
            if (j+1<n&&p.charAt(j+1)=='*'){
                //2.1
                res=dp(s,i,p,j+2);
            }else {
                res=false;
            }
        }
        return res;
    }

    public boolean match (String str, String pattern) {
        return dp(str,0,pattern,0);
    }

    /**==============================================================================================================================================
     * JZ71 跳台阶扩展问题
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
     * dp[i]=dp[i-1]+dp[i-2]+...dp[0]=(dp[i-2]+dp[i-3]...dp[0])+dp[i-2]+...dp[0]=2*dp[i-1];
     * 即：dp[i]=2^(i-1);
     *  */
    public int jumpFloorII(int target) {
        if (target==0||target==1)return 1;
        //左移一位为乘2
        return 1<<(target-1);
    }


    /**==============================================================================================================================================
     * JZ70 矩形覆盖
     * 我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？
     * 确定了高度：对于n=1时有1种，n=2时有2种，n=3时有3种，n=4时考虑两种情况
     *                                                1、在n=3的后面竖着放一个，一共有3种
     *                                                2、在n=2的后面横着放；两个也可以，一共有2种
     * 推到出：f[i]=f[i-1]+f[i-2]----斐波那契数列
     *  */
    public int rectCover(int target) {
        if (target<=3) return target;
        int f_1=3,f_2=2;
        for (int i = 4; i <= target; i++) {
            int f=f_2+f_1;
            f_2=f_1;f_1=f;
        }
        return f_1;
    }


    /**==============================================================================================================================================
     * JZ63 买卖股票的最好时机(一)
     * 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益.
     * 你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天--------------k=1,无手续费
     * 套模板：每天都有三种「选择」：买入、卖出、无操作，我们用 buy , sell , rest 表示这三种选择。
     *        dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])  表示：第i天没有持有股票的最大交易次数为k时的最大收益：
     *                    要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
     *                    要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
     *        dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) 第i天持有股票的最大交易次数为k时的最大收益：
     *                     要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
     *                     要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
     * 最大子数组的和：计算每一天的差值，找出差值序列的最大子数组和
     *  */
    public int maxProfit (int[] prices) {
        if (prices.length<2)return 0;
        int dp_pre=prices[1]-prices[0];
        int res=dp_pre;
        for (int i = 2; i < prices.length; i++) {
            int dif=prices[i]-prices[i-1];
            int dp=Math.max(dp_pre+dif,dif);
            dp_pre=dp;
            res=Math.max(res,dp);
        }
        return res>0?res:0;
    }

    /**==============================================================================================================================================
     * JZ47 礼物的最大价值
     * 在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，
     * 并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
     * lcs的算法：dp[i][j]表示从[0,0]到达[i,j]时可以获得的礼物的最大价值
     * dp[i][j]=max(dp[i-1][j],dp[i,j-1])+grid[i][j]
     *  */
    public int maxValue (int[][] grid) {
        if (grid.length==0||grid[0].length==0)return 0;
        int m=grid.length,n=grid[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }

    /**==============================================================================================================================================
     * JZ48 最长不含重复字符的子字符串
     * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
     * 滑动窗口：需要用一个set记录窗口内包含的元素，当每次左指针移动时需要更新字串长度的值
     *  */
    public int lengthOfLongestSubstring (String s) {
        if (s.length()<=1) return s.length();
        Set<Character> set=new HashSet<>();
        int left=0,right=0;
        int count=1;
        while (right<s.length()){
            //c为即将移入窗口的字符
            char c=s.charAt(right);
            right++;
            //进行窗口内数据的更新
            if (!set.contains(c)){
                set.add(c);
                count=Math.max(count,right-left);
            }else {
                //左侧窗口收缩
                while (set.contains(c)){
                    char d=s.charAt(left);
                    set.remove(d);
                    left++;
                    //进行窗口内数据的一系列更新
                }
                set.add(c);
            }
        }
        return count;
    }

    /**==============================================================================================================================================
     * JZ46 把数字翻译成字符串
     * 有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。现在给一串数字，返回有多少种可能的译码结果
     * dp[i]表示前i个字符的译码方式，对于第i个字符可以是和前一个数字一起译码，或者是单独译码。若其可以满足和前一个一起译码的方式，则可以+2，若是不能，则只能是单独译码
     *  */
    public int solve (String nums) {
        int n=nums.length();
        if (n==1) return nums.charAt(0)=='0'?0:1;
        int[] dp=new int[n];
        dp[0]=nums.charAt(0)=='0'?0:1;
        for (int i = 1; i < n; i++) {
            //先判断当前字符可否单独解码
            if (nums.charAt(i)!='0'){
                dp[i]=dp[i-1];
            }
            int num=Integer.parseInt(nums.substring(i-1,i+1));
            //判断是否可以和前一个字符组合解码
            if (num>=10&&num<=26){
                if (i==1){
                    dp[i]+=1;
                }else {
                    dp[i]+=dp[i-2];
                }
            }
        }
        return dp[n-1];
    }
}
